// https://leetcode.cn/problems/combination-sum-iv/description/

// 算法思路总结：
// 1. 动态规划解决组合总和IV问题（排列数）
// 2. 状态定义：dp[i]表示凑出目标i的排列数
// 3. 外层遍历目标值，内层遍历数字（求排列数）
// 4. 状态转移：dp[i] += dp[i - num]（使用unsigned防溢出）
// 5. 数字可重复使用，顺序不同视为不同排列
// 6. 时间复杂度：O(n×target)，空间复杂度：O(target)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>

class Solution 
{
public:
    int combinationSum4(vector<int>& nums, int target) 
    {
        vector<unsigned int> dp(target + 1, 0);
        dp[0] = 1;

        for (int i = 1 ; i <= target ; i++)
        {
            for (const int& num : nums)
            {
                if (i >= num)
                {
                    dp[i] += dp[i - num]; 
                }
            }
        }

        return dp[target];
    }
};

int main()
{
    vector<int> nums1 = {1, 2, 3}, nums2 = {9};
    int target1 = 4, target2 = 3;

    Solution sol;

    cout << sol.combinationSum4(nums1, target1) << endl;
    cout << sol.combinationSum4(nums2, target2) << endl;

    return 0;
}